Previous | 
Home
Section: Software
BaPCod – a generic Branch-and-Price Code
Participants : Romain Leguay [Software Engineer] , Pierre Pesneau, Ruslan Sadykov, François Vanderbeck [correspondant] .
BaPCod is a prototype code that solves Mixed Integer Programs (MIP) by application of a Dantzig-Wolfe reformulation technique. The reformulated problem is solved using a branch-and-price (column generation) algorithm. This software platform, made of C++ classes, offers a “black-box” implementation that does not require user input and is not application specific. The features are
the automation of the Dantzig-Wolfe reformulation process (the user defines a mixed integer programming problem in terms of variables and constraints, identifies subproblems, and can provide the associated solvers if available, but he does not need to explicitly define the reformulation, the explicit form of the columns, their reduced cost, or the Lagrangian bounds).
a default column generation procedure with standard initialization and stabilization (it may offer a selection of solvers for the master) – the issue of stabilization is discussed in [1] , and
a default branching scheme – recent progress has been made on the issue of generic branching scheme in [23] .
default primal heuristics specially developed for use in a decomposition framework [58] .
The prototype software was/is used as background solver for 5 PhD thesis. It also served as the framework for our comparative study in a INRIA collaborative research action [1] . It has been experimented by two of our industrial partners, Exeo Solutions (Bayonne), on an inventory routing problem, and Orange Lab (France Telecom, Paris) on network design problems, time tabling problme by EURODECISION and it is currently being tested by the University Paris 6 and EDF. The prototype also enables us to be very responsive in our industrial contact.
See also the web page https://wiki.bordeaux.inria.fr/realopt/pmwiki.php/Project/BaPCod .